Introduction to Computer Networks

我们要学些什么？

• three “networking” topics:

  • 

• 我们要学些什么？

  • To learn how the Internet works
  • To learn the fundamentals of computer networks
    
    • What hard problems must they solve?
    • What design strategies have proven valuable?
  • key problems
    
    • 

protocol and layering

• why do we need protocol and layering

  • manage complexity
  • reuse
  • information hiding

• what is protocol and layering?

  • 
  • Protocols and layering is the main structuring method used to divide up network functionality
  • Each instance of a protocol talks virtually to its peer using the protocol
  • Each instance of a protocol uses only the services of the lower layer

• Encapsulation

  • Encapsulation is the mechanism used to effect protocol layering
    
    • Lower layer wraps higher layer content, adding its own information to make a new message for delivery
    • Like sending a letter in an envelope; postal service doesn’t look inside

Network Components

• component Names
  
  • 
• Network names by scale
  
  • 

• Network Boundaries

  • 
  • interface 1
    
    • Sockets are widely used in practice
  • interface 2
    
    • Traceroute can peek in the network

• Metcalfe’s Law

  • The value of a network of N nodes is proportional to

History of the Internet

The Socket API

Reference Models

• What functionality should we implement at which layer?
  
  • 

Physical Layer

Media

• Wires
  
  • Twisted Pair
  • Coaxial Cable
• Fiber (fiber optic cables)
  
  • Two varieties: multi-mode (shorter links, cheaper) and single-mode (up to ~100 km)
• Wireless
  
  • In many directions, unlike a wire, to potentially many receivers
  • Nearby signals (same freq.) interfere at a receiver; need to coordinate use

Signals

• What happens to a signal as it passes over a wire?
  
  • The signal is delayed (propagates at ⅔C)
  • The signal is attenuated (goes for m to km)
  • Frequencies above a cutoff are highly attenuated
  • Noise is added to the signal (later, causes errors)

Modulation

• NRZ
• NRZI
• 4B/5B
• Manchester coding

baseband and passband

• baseband
  
  • Signal is sent directly on a wire
• Passband
  
  • These signals do not propagate well on fiber / wireless, Need to send at higher frequencies
  • modify carrier by
    
    • Amplitude
    • frequency
    • phase

Fundamental Limits

• Nyquist Limit(no noise channel)
  
  • 
• Shannon limit(noise channel)
  
  • 
• Wired/Wireless Perspective
  
  • 
  • 

Link Layer

Framing

• Byte count
  
  • 
  • Difficult to re-synchronize after framing error
• Byte stuffing
  
  • Have a special flag byte value that means start/end of frame
  • Replace (“stuff”) the flag inside the frame with an escape code
  • overhead
• Bit stuffing
  
  • Call a flag six consecutive 1s
  • On transmit, after five 1s in the data, insert a 0
  • On receive, a 0 after five 1s is deleted
• practical link protocol(PPP)
  
  • 

How we deal with errors?

error detection + retransmit

• Parity
• Checksums
  
  • IP, TCP, UDP … but it is weak
• CRCs
  
  • CRCs are widely used on links

error correction

• Hamming code
• Convolutional codes
• Low Density Parity Check

Retransmissions

• ARQ
  
  • Receiver automatically acknowledges correct frames with an ACK
  • Sender automatically resends after a timeout, until an ACK is received
• Two non-trivial issues
  
  • How long to set the timeout?
    
    • Not too big (link goes idle)
    • Not too small (spurious resend)
  • How to avoid accepting duplicate frames as new frames?
    
    • Sequence Numbers
• Sliding Window
  
  • Allows W frames to be outstanding

Multiple Access

statistical multiplexing

• Time Division Multiplexing (TDM)
• Frequency Division Multiplexing (FDM)
• Network traffic is bursty, Inefficient to always allocate user their ON needs with TDM/FDM. — Multiple Access

Randomized. Nodes randomize their resource access attempts

• ALOHA Protocol
  
  • 
  • 
• Classic Ethernet (Carrier Sense Multiple Access)
  
  • Improve ALOHA by listening for activity before we send (Doh!)
  • Still possible to listen and hear nothing when another node is sending because of delay
  • CSMA/CD (with Collision Detection)
    
    • Can reduce the cost of collisions by detecting them and aborting (Jam) the rest of the frame time
    • Time window in which a node may hear of a collision is 2D seconds
    • Impose a minimum frame size that lasts for 2D seconds( Ethernet minimum frame is 64 bytes)
    • Binary Exponential Backoff (BEB)
      
      • 1st collision, wait 0 or 1 frame times
      • 2nd collision, wait from 0 to 3 times
      • ······

• Wireless Multiple Access

  • 
  • Hidden Terminals
    
    • 
  • Exposed Terminals
    
    • 

• Good for low load situations

Contention-free. Nodes order their resource access attempts

• They define an order in which nodes get a chance to send. We just need some ordering
  
  • Token Ring
    
    • 
    • Predictable service, easily extended to guaranteed quality of service
    • Higher overhead at low load
  • node addresses

Switching

error detection vs error correction

Network Layer

Overview

Link Layer’s problem

Network Layer’s Solution

Topics

Network Service models

• 
• Both models are implemented with store-and-forward packet switching
  
  • Routers receive a complete packet, storing it temporarily if necessary before forwarding it onwards
• Internet的网络层协议（IP）采用的是数据报模型
• Datagram Model
  
  • Packets contain a destination address; each router uses it to forward each packet, possibly on different paths
• Virtual Circuit Model
  
  • 
• Datagrams vs Virtual Circuits
  
  • 
• MPLS
  
  • 

Internetworking

• networks differ in many ways
  
  • Service model (datagrams, VCs)
  • Addressing (what kind)
  • QOS (priorities, no priorities)
  • Packet sizes
  • Security (whether encrypted)
• solution: IP
  
  • 
• lowest common denominator
  
  • Asks little of lower-layer networks
  • Gives little as a higher layer service

IP Prefixes

• Addresses are allocated in blocks called prefixes

  • Addresses in an L-bit prefix have the same top L bits
  • There are addresses aligned on boundary

• Public IP addresses

  • Valid destination on the global Internet
  • Must be allocated to you before use

• Private IP addresses

  • an be used freely within private networks (home, small company)
  • 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16
  • Need public IP address(es) and NAT to connect to global Internet

• IP Address allocated

  • 

Forwarding

• Longest Matching Prefix
  
  • For each packet, find the longest prefix that contains the destination address, i.e., the most specific entry
  • Forward the packet to the next hop router for that prefix
• host也可能需要转发，但是这个转发跟路由没有关系
  
  • 

Helping IP with ARP, DHCP

• Filling in the gaps we need to make for IP forwarding work in practice

  • Getting IP addresses (DHCP)
  • Mapping IP to link addresses (ARP)

• DHCP

  • 
  • 
  • 
• ARP
  
  • 
  • 
  • 

Packet Fragmentation

• How do we connect networks with different maximum packet sizes?
• Solutions
  
  • 
  • 
• fragment
  
  • 
  • 
• Path MTU Discovery
  
  • 
  • 

Error Handling with ICMP

• What happens when something goes wrong during forwarding? — ICMP
• ICMP is a companion protocol to IP
  
  • They are implemented together
  • Sits on top of IP (IP Protocol=1)
• 
• 
• 

IPV6

• 
• IPv6 Transition
  
  • Fundamentally incompatible with IPv4
  • Dual stack (speak IPv4 and IPv6)
  • Translators (convert packets)
  • Tunnels (carry IPv6 over IPv4)
    
    • 

NAT

• NAT is widely used at the edges of the network
• 
• 

IP字段解释

Routing

• 实际上，路由完成的就是一个带宽分配的工作
  
  • 
• Delivery Models
  
  • 
• Goals of Routing Algorithms
  
  • 
• Rules of Routing Algorithms
  
  • 

Distance Vector Routing

• Simple, early routing approach
  
  • Used in ARPANET, and RIP
• 
• News travels one hop per exchange
• problems:
  
  • Count to infinity
    
    • 
• solution
  
  • poison reverse
    
    • Don’t send route back to where you learned it from
  • Split horizon

Link State

• flooding

  • 
  • 

• Link-State Routing

  • 
  • 
  • problems
    
    • 
    • 
    • 

• 

Equal-Cost Multi-Path Routing

• Allow multiple routing paths from node to destination be used at once
  
  • Topology has them for redundancy
  • Using them can improve performance
• 
• 

Combining Hosts and Routers

• How routing protocols work with IP?
  
  • 
• 

Hierarchical Routing

• Introduce a larger routing unit
  
  • IP prefix (hosts) <— from one host
  • Region, e.g., ISP network
• 

IP Prefix Aggregation and Subnets

Routing with Multiple Parties

Border Gateway Protocol

• BGP is the protocol that computes interdomain routes in the Internet

  • Path vector, a kind of distance vector
  • 

• 

• 
• 

Transport Layer

TCP connection and disconnection

• tcp and udp

  • 
  • 

• connection establishment

  • 
  • 

• connection release

  • 
  • 

• Sliding Window Protocol

  • Go-Back-N
  • Selective Repeat
  • 
  • 

• flow control

  • Adding flow control to the sliding window algorithm
    
    • 
  • Sender uses the lower of the sliding window and flow control window (WIN) as the effective window size

• adaptive time-out

  • How to set the timeout for sending a retransmission
  • 

• tcp header

  • 
  • Ports identify apps (socket API)
  • SEQ/ACK used for sliding window
  • SYN/FIN/RST flags for connections
  • Window size for flow control

Congestion Control

• 什么是网络拥塞？
  
  • 
• 网络拥塞有什么后果？
  
  • 
• 控制网络拥塞本质上是一个带宽分配的问题，怎么在保证效率的同时保证公平？
  
  • 
  • 
• AIMD
  
  • 
  • 
  • 

ACK Clocking

• 实际上是一个滑动窗口，保证reliability
• 

slow start

Fast Retransmit / Fast Recovery